#include <cstdio>

int main( )
{
    int q, n, m, p[ 101 ], h[ 101 ], c[ 101 ], i, j, k, f[ 101 ], maxn;
    scanf("%d", &q);
    while ( q-- )
    {
        scanf("%d%d", &n, &m);
        for ( i = 0; i < m; i++ )
            scanf("%d%d%d", &p[ i ], &h[ i ], &c[ i ]);
        for ( i = 0; i <= n; i++ )
            f[ i ] = 0;
        maxn = 0;
        for ( i = 0; i < m; i++ )
            for ( j = 0; j < c[ i ]; j++ )
                for ( k = n; k >= p[ i ]; k-- )
                {
                    if ( f[ k ] < f[ k - p[ i ] ] + h[ i ] )
                        f[ k ] = f[ k - p[ i ] ] + h[ i ];
                    if ( f[ k ] > maxn )
                        maxn = f[ k ];
                }
        printf("%d\n", maxn);
    }
    return 0;
}
